//
// Created by 25238 on 2024-01-13.
//

#ifndef SELECTION_SORT_QUICKSORT_H
#define SELECTION_SORT_QUICKSORT_H

#include <iostream>
#include <algorithm>

using namespace std;

// 对arr[l..r]部分进行partition操作
template <typename T>
int __partition(T arr[], int l, int r){
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    // arr[l + 1 ... j] < v , arr[j + l ... i] > v
    int j = l;
    for(int i = l + 1; i <= r; i++)
        if(arr[i] < v)
            swap(arr[++j], arr[i]);
    swap(arr[l], arr[j]);

    return j;
}

// 对于arr[l...r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r){
    if(l >= r)
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p+1, r);
}


template <typename T>
void quickSort(T arr[], int n){
    srand(time(NULL));
    __quickSort(arr, 0, n - 1);
}

// ========================================================================

// 对arr[l..r]部分进行partition操作
template <typename T>
int __partition2(T arr[], int l, int r){
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    // arr[l + 1 ... i] <= v , arr[j ... r] >= v
    int i = l + 1, j = r;
    while(true){
        while (i <= r && arr[i] < v) i++;
        while (j >= l + 1 && arr[j] > v) j--;
        if(i > j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);

    return j;
}

// 对于arr[l...r]部分进行快速排序
template<typename T>
void __quickSort2(T arr[], int l, int r){
    if(l >= r)
        return;

    int p = __partition2(arr, l, r);
    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p+1, r);
}


template <typename T>
void quickSort2(T arr[], int n){
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

// ========================================================================

template <typename T>
void __quickSort3(T arr[], int l, int r){
    if(l >= r)
        return;
    // partition
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    int lt = l;     // arr[l + 1 .. lt] < v
    int gt = r + 1; // arr[gt .. r] > v
    int i = l + 1;  // arr[lt + 1 .. i] == v
    while(i < gt){
        if(arr[i] < v)
            swap(arr[i++], arr[++lt]);
        else if(arr[i] > v)
            swap(arr[i], arr[--gt]);
        else         // arr[i] == v
            ++i;
    }
    swap(arr[l], arr[lt]);
    __quickSort3(arr, l, lt - 1);
    __quickSort3(arr, gt, r);
}

template <typename T>
void quickSort3(T arr[], int n){
    srand(time(NULL));
    __quickSort3(arr, 0, n - 1);
}

#endif //SELECTION_SORT_QUICKSORT_H
